package com.zlk.algorithm.algorithm.unionAndFind;

import org.junit.Test;

import java.util.Stack;

/**
 * @program: algorithm
 * @ClassName NumberOfIslands
 * @description:岛问题（递归解法 + 并查集解法 + 并行解法） 给定一个二维数组matrix，
 * 里面的值不是1就是0，上、下、左、右相邻的1认为是一片岛，返回matrix中岛的数量
 *
 * https://leetcode.cn/problems/number-of-islands/
 * @author: slfang
 * @create: 2024-03-07 15:55
 * @Version 1.0
 **/
public class NumberOfIslands {

    @Test
    public void test(){
        char[][] grid= new char[4][5];
        for (int i = 0; i < 4; i++) {
            grid[0] = new char[]{'1','1','1','1','0'};
            grid[1] = new char[]{'1','1','0','1','0'};
            grid[2] = new char[]{'1','1','0','0','0'};
            grid[3] = new char[]{'0','0','0','0','0'};
        }
        System.out.println(numIslands(grid));
    }


    public int numIslands(char[][] grid) {
        build(grid);
        int n = grid.length;
        int m = grid[0].length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(grid[i][j]=='1'){
                    if(j-1>=0&&grid[i][j - 1] == '1'){
                        union(index(i,j),index(i,j-1));
                    }
                    if(i-1>=0&& grid[i - 1][j] == '1'){
                        union(index(i,j),index(i-1,j));
                    }
                }
            }
        }
        return sets;
    }

    private void union(int a, int b) {
        if(!isSameSet(a,b)){
            int fa = findFather(a);
            int fb = findFather(b);
            int sizeA = size[fa];
            int sizeB = size[fb];
            if(sizeA>=sizeB){
                size[fa] = sizeA+sizeB;
                father[fb] =fa;
            }else{
                size[fb] = sizeA+sizeB;
                father[fa] =fb;
            }
            sets--;
        }
    }

    private boolean isSameSet(int a, int b) {
        return findFather(a)==findFather(b);
    }

    private int findFather(int cur) {
        int size = 0;
        while (cur!=father[cur]){
            help[size++] = cur;
            cur = father[cur];
        }
        size--;
        while (size>=0){
            father[help[size--]]=cur;
        }
        return cur;
    }


    int MAXN = 100001;
    int[] father=new int[MAXN];
    int[] size = new int[MAXN];

    int[] help = new int[MAXN];


    int sets=0;
    int col ;

    private void build(char[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        col = m;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(grid[i][j]=='1'){
                    int index = index(i,j);
                    father[index] = index;
                    size[index] = 1;
                    sets++;
                }
            }
        }
    }

    private int index(int i, int j) {
        return i*col+j;
    }

}
